The present invention relates to the design of arithmetic units in digital computer systems and, more particularly, to the design of binary adders.
Arithmetic operations in computer systems, such as addition and subtraction, are performed on two operands, each having a given number of bits (e.g., N bits), the operations yielding an N-bit result.
Because a great number of arithmetic operations can be performed by high speed digital computers in a relatively short time interval (e.g., one second), the time required to perform any one of such operations can become a significant factor when multiplied by the number of operations per second. Designers are therefore obliged to invent ever faster formulations to perform arithmetic operations.
Conventional addition functions, such as carry (or borrow) generate and carry propagate, are described in COMPUTER ARTITHMETIC PRINCIPLES, ARCHITECTURE, AND DESIGN, by Kai Hwang. These functions generally depend on two paths: one that produces carries into a bit position and one that produces a half-sum. The conventional recursive formulas are shown below and are derived as follows: ##EQU1##
For every position i a carry is received from position i+1 to be added with A.sub.i, B.sub.i. In essence: ##EQU2## where C.sub.i+1 is the carry bit from position i+1.
The maximum value for each individual operand is one. Therefore, MAX [A.sub.i +B.sub.i +C.sub.i+1 [=1+1+1=3. Since two bits are required to represent the number three (11, in binary code), a carry to the next position is generated.
All combinations are shown below in Table 1.
TABLE I ______________________________________ C.sub.i+1 A.sub.i B.sub.i S.sub.i C.sub.i ______________________________________ (1) 0 0 0 0 0 (2) 0 0 1 1 0 (3) 0 1 0 1 0 (4) 0 1 1 0 1 (5) 1 0 0 1 0 (6) 1 0 1 0 1 (7) 1 1 0 0 1 (8) 1 1 1 1 1 ______________________________________ 0 + 0 + 0 = 0 = &gt;S.sub.i = 0, C.sub.i = 0 1 + 1 + 0 = 2 = &gt;S.sub.i = 0, C.sub.i = 1